import random

from Crypto.Util.number import *


def genkeys():
    q = getPrime(9)
    k = 0
    while True:
        p = k * q + 1
        if isPrime(p):
            print(p)
            break
    g = random.randint(0,p//2)
    print(q)
    return g, q, p

def myhash(b,g,q,p):
    h = pow(g,b%q,p)
    return h


flag = 'xxx'
assert len(flag) == 40
f = open('hint.txt','w')
g,q,p = genkeys()
print(g,q,p)
# g = 47 , q = 257 , p = 1543

outside = []
for i in range(len(flag)):
    tmp = bytes_to_long(flag[i].encode())
    h = myhash(tmp,g,q,p)
    if i == 5 or i ==6 or i == 9:
        outside.append(h)
        continue
    f.write(str(h)+' ')

hint2 = outside[0] * outside[1] * outside[2]
assert  414966000 < hint2 < 414969000

G = 0
for i in flag:
    G = G + ord(i)
H = myhash(G,g,q,p)
print(H)
# 1403
# DASCTF{4818caa75b2d7586e96f4c552ded3654}
